package 热题100;

import java.util.ArrayDeque;
import java.util.Deque;

public class 热题20有效的括号 {

    /**
     * 使用栈来解决括号匹配问题
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        char[] ch = s.toCharArray();
        if ((ch.length & 1) == 1) return false;
        for (int i = 0; i < ch.length; i++) {
            //如果开括号，入栈
            if (ch[i] == '(' || ch[i] == '{' || ch[i] == '['){
                deque.push(ch[i]);
            }else {
                //如果遇到了比括号，但是栈为空，直接返回fasle
                if (deque.isEmpty()){
                    return false;
                }

                //说明是闭括号，如果栈顶和当前的字符匹配，则出栈继续遍历
                if (ch[i] == ')' && deque.peek() == '('){
                    deque.pop();
                }else if (ch[i] == '}' && deque.peek() == '{'){
                    deque.pop();
                }else if (ch[i] == ']' && deque.peek() == '['){
                    deque.pop();
                }else {
                    return false;
                }
            }
        }
        //最终所有的串遍历结束，如果栈不为空，说明开括号多了，返回fasle
        if (deque.size() != 0){
            return false;
        }
        //否则返回true；
        return true;
    }
}
